package BS_1300;

import java.util.Arrays;

public class Solution {
	public int findBestValue(int[] arr, int target) {
		Arrays.sort(arr);
		int[] prefix = new int[arr.length + 1];
		for (int i = 1; i < arr.length; i++) {
			prefix[i] = prefix[i - 1] + arr[i - 1];
		}
		int right = arr[arr.length - 1];
		int ans = 0, diff = target;
		for (int i = 1; i <= right; i++) {
			int index = BS(arr, i);
			int cur=prefix[index]+(arr.length-index)*i;
			if (Math.abs(cur-target)<diff) {
				ans=i;
				diff=Math.abs(cur-target);
			}
		}
		return ans;

	}

	private int BS(int[] arr, int target) {
		// TODO Auto-generated method stub
		int left = 0, right = arr.length - 1;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (arr[mid] == target) {
				return mid;
			}

			if (arr[mid] > target) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}

		}

		return left;
	}
}
